Лемма о жадной оценке

Пусть $G$ — произвольный граф, $\Delta(G)$ — максимальная степень вершины в $G$. Тогда $\chi(G) \leq \Delta(G) + 1$.

Раскрасим $G$ следующим жадным алгоритмом: вершины $G$ упорядочиваются в список произвольным образом. Очередная вершина $v$ красится в наименьший из цветов, не совпадающих с цветами уже покрашенных смежных вершин. Алгоритм строит правильную раскраску. Любая вершина имеет не более $\Delta(G)$ окрашенных соседей и получает цвет $\leq \Delta(G) + 1$. $\square$

Если $G$ — неполный граф и $\Delta(G) \ge 3$, то $\chi(G) \le \Delta(G)$.